1. Field of the Invention
The present invention relates to auctions and, more particularly, to winner determination in forward auctions, reverse auctions and exchanges.
2. Description of Related Art
Combinatorial auctions where bidders can bid on bundles of items can be desirable market mechanisms when the items exhibit complementarily or substitutability, so the bidder's valuations for bundles are not additive. One of the problems with these otherwise desirable mechanisms is that determining the winners is computationally complex. There has been a recent surge of interest in winner determination algorithms for such markets.
Another problem, which has received less attention, is that combinatorial auctions require potentially every bundle to be bid on, and there are exponentially many bundles. This is complex because a bidder may need to invest considerable effort or computation into determining each valuation. It can also be undesirable from the perspective of revealing unnecessary private information and from the perspective of unnecessary communication.
It is, therefore, desirable to identify a topological structure that is inherent in combinatorial auctions that can be used to intelligently ask only relevant questions about the bidders' preferences while still finding the optimal (welfare-maximizing and/or Pareto-efficient) solution(s). It is also desirable to provide building blocks for a design of an auctioneer that interrogates each bidder intelligently regarding the bidder's preferences, and optimally assimilates the returned information in order to narrow down the set of potentially desirable allocations, and decide which questions to ask the bidders next to further narrow down the set of potentially desirable allocations.